package q287_findDuplicate;

import java.util.Arrays;

public class Solution_1 {
    /*
    题中已经指定了范围为1 - n中一个数至少重复了一次 所以我们只需要将数字移动到它们本来应该出现的位置
    然后不断循环 直到某一次交换后发现 交换的两个位置数字相同 就能够找到该数字
     */
    public int findDuplicate(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            // if (nums[i] == nums[nums[i] - 1] && nums[i] != i + 1) return nums[i];
            while (nums[i] != nums[nums[i] - 1]) {
                int temp = nums[i], temp2 = nums[nums[i] - 1];
                nums[i] = temp2;
                nums[temp - 1] = temp;
            }
            if (nums[i] == nums[nums[i] - 1] && nums[i] != i + 1) return nums[i];
        }
        return 0;
    }

    public static void main(String[] args) {
        int[] nums = {4,4,17,15,2,1,19,11,12,13,3,18,4,4,5,9,7,14,4,16};
        Solution_1 s = new Solution_1();
        System.out.println(s.findDuplicate(nums));
        System.out.println(Arrays.toString(nums));
    }
}
